/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/longest-common-prefix
@Language: C++
@Datetime: 16-02-09 05:56
*/

class Solution {
    struct TrieNode {
        static const int ALPHA = 256;
        int count;
        TrieNode * nodes[ALPHA];
        TrieNode() {
            for(int i=0;i<ALPHA;++i)
                nodes[i]=NULL;
            count=1;
        }
    };
    TrieNode *root;
    void insert(string &word,int id) {
        TrieNode *tn = root;
        for(int i=0;i<word.length();tn=tn->nodes[word[i]],++i)
            if (tn->nodes[word[i]]==NULL){
                if (id==0)
                    tn->nodes[word[i]] = new TrieNode();
				else
					break;
            }
            else
                tn->nodes[word[i]]->count++;
    }
    void destroy(TrieNode *tn){
        if (tn==NULL)
            return;
        for(int i=0;i<TrieNode::ALPHA;++i)
            destroy(tn->nodes[i]);
        delete tn;
    }
public:    
    /**
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    string longestCommonPrefix(vector<string> &strs) {
        // write your code here
        root = new TrieNode();
        for(int i=0;i<strs.size();++i)
            insert(strs[i],i);
        string s;
        TrieNode *t=root;
        bool found=true;
        while(found){
            found=false;
            for(int i=0;i<TrieNode::ALPHA;++i)
                if (t->nodes[i] && t->nodes[i]->count==strs.size()){
                    t = t->nodes[i];
                    found=true;
                    s.push_back((char)i);
                    break;
                }
        }
                
        destroy(root);
        return s;
    }
};